//
//  50_X的N次方.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/15.
/*
 https://leetcode.cn/problems/powx-n/description/
 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 示例 1：
 输入：x = 2.00000, n = 10
 输出：1024.00000
 示例 2：
 输入：x = 2.10000, n = 3
 输出：9.26100
 示例 3：
 输入：x = 2.00000, n = -2
 输出：0.25000
 解释：2-2 = 1/22 = 1/4 = 0.25

 */

import UIKit

class GetXPow: NSObject {
    
    func QA() {
        print(myPow(2.00000, 10))
        print(myPow(2.1000, 3))
        print(myPow(2.00000, -2))
        print(myPow(0.25, -2))
        print(myPow(-2.00, 2))

    }
    
    /// 分治(迭代) 空间复杂度O（1）,时间复杂度logN
    func myPow(_ x: Double, _ n: Int) -> Double {
        if n == 0 { return 1 }
        // 判断n的正负值
        var m = n < 0 ? -n : n
        var result = 1.0
        var x = x
        while m > 0 {
            if m & 1 == 1 {
                result *= x
            }
            x *= x
            m = m >> 1
        }
        return n < 0 ? (1/result) : (result)
    }
    
    /// 分治(递归) 空间复杂度O（logn）,时间复杂度logN
    func myPow2(_ x: Double, _ n: Int) -> Double {
        if n == 0 { return 1 }
        // 判断n的正负值
        let m = n < 0 ? -n : n
        // 判断 n 是奇数还是偶数 true 是奇数
        let ood = m & 1 == 1
        let ban = myPow2(x, m >> 1)
        let result = ood ? (ban * ban * x) : (ban * ban)
        
        return n < 0 ? (1/result) : (result)
    }

    func myPow1(_ x: Double, _ n: Int) -> Double {
        if n == 0 { return x }
        var result = 1.0
        var m = n < 0 ? -n : n
        while m > 0 {
            result = result * Double(m)
            m -= 1
        }
        return  n > 0 ? result : 1/result
    }
}
